package demo1;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //下一个排列
    public void nextPermutation(int[] nums) {
        if(nums.length < 2) return;

        // 先从后向前找第一个相邻且升序的一对数：nums[i] < nums[j]此时意味着nums[i]是可以被[j, end]中的较大数替换的
        int i = nums.length - 2;
        int j = nums.length - 1;
        while(i >= 0 && nums[i] >= nums[j]) {
            i--;
            j--;
        }

        // 如果没有找到，说明整个数组是逆序的，已经达到最大字典排序，需要重新转为升序排列
        if(i < 0) {
            reverse(0, nums.length, nums);
            return;
        }

        // 此时[j, end]中的数为降序排列，需要从后往前找到第一个大于nums[i]的数nums[k]，以减少增加幅度
        int k = nums.length - 1;
        while(k >= j && nums[k] <= nums[i]) k--;

        // 将nums[i]与nums[k] 交换
        swap(i, k, nums);
        // System.out.println(Arrays.toString(nums));
        // System.out.println("i = " + i + ", j = " + j + ", k = " + k);

        // 将[j, end]的数升序排列
        reverse(j, nums.length - 1, nums);
    }

    private void swap(int i, int k, int[] nums) {
        int temp = nums[i];
        nums[i] = nums[k];
        nums[k] = temp;
    }

    private void reverse(int start, int end, int[] nums) {
        for(int l = start; l < start + (end - start + 1) / 2; l++) {
            swap(l, start + nums.length - l - 1, nums);
        }
    }
}
